package divideconquer;

import java.util.Random;

public class QuickSort {

	static Random ran = new Random();

	public static void sort(int[] a, int i, int j) {
		if (i >= j)
			return;
		int p = partition(a, i, j);
		sort(a, i, p - 1);
		sort(a, p + 1, j);
	}

	static int partition(int[] a, int i, int j) {
		int p = ran.nextInt(j - i + 1) + i;
		swap(a, p, j);
		p = j;
		j = i;
		while (j <= p) {
			if (a[j] <= a[p]) {
				swap(a, i++, j);
			}
			j++;
		}
		return i - 1;
	}

	static void swap(int[] a, int i, int j) {
		if (i != j) {
			a[i] ^= a[j];
			a[j] ^= a[i];
			a[i] ^= a[j];
		}
	}

	public static void main(String[] args) {
		int n = 50;
		int[] a = new int[n];
		for (int i = 0; i < n; ++i) {
			a[i] = ran.nextInt(100);
		}
		sort(a, 0, n - 1);
		for (int i : a) {
			System.out.print(i + " ");
		}
	}

}
